package hot100;


/*
 * Author：江松
 * Date：2023/4/6 15:20
 *
 回文链表:
 1,用数组存放遍历链表结果，然后用双指针判断数组  O(N) O(N)
 ×2，栈存储还需要讨论奇偶，O(N/2) O(N)
 3,O(1) O(N)
 用快慢指针找到中间点，然后翻转它后面的部分  ，然后进行比较
 */

import java.util.ArrayList;

public class Main234 {
      public class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }


    public ListNode findMid(ListNode head){
        ListNode slow=head,fast=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }

    public ListNode reverseList(ListNode head){
        ListNode p=head,q=null;
        while(p!=null){
            ListNode t=p;
            p=p.next;
            t.next=q;
            q=t;
        }
        return q;
    }

    public boolean isPalindrome(ListNode head) {
        if(head==null)return true;
        //得到中点并翻转其后边部分
        ListNode mid=findMid(head);
        //得到翻转后的头节点
        ListNode sec=reverseList(mid.next);

        ListNode st=head;
        ListNode t=sec;
        boolean res=true;
        while(res&&t!=null){
            if(st.val!=t.val)res=false;
            st=st.next;
            t=t.next;
        }
        //还原
        mid.next=reverseList(sec);
        return res;
    }
 /*
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer>arr=new ArrayList<>();
        ListNode p=head;
        while(p!=null){
            arr.add(p.val);
            p=p.next;
        }
        int i=0,j=arr.size()-1;
        while(i<j){
            if(arr.get(i)!=arr.get(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    */
}
